package demo.practice.dp;

public class P213 {
    public int rob(int[] nums) {

        //和之前的普通 打家劫舍 I 思路相似
        //dp[0]= nums[0]
        //dp[1]= Math.max(nums[0],nums[1])

        //第i个dp
        // 1. i不是最后一个元素 dp[i]= Math.max(dp[i-2]+ nums[i],dp[i-1])
        //  2. i是最后一个元素  不选是Ok 的 dp[i-1]  ， 选了i则不能选 nums[0]     因为我们要找的就是


        if (nums == null || nums.length == 0)
            return -1;

        if (nums.length == 1) {
            return nums[0];
        }


        int dp1[] = new int[nums.length];
        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0],nums[1]);

        for(int i=2;i<dp1.length;i++){

            if(i==dp1.length-1){
                //因为dp1中的dp1[0]是选择了nums[0]的，所以这里nums[i]只能不选
                dp1[i]= dp1[i-1];
            }else{
                dp1[i]= Math.max(dp1[i-2]+ nums[i],dp1[i-1]);
            }
        }

        int dp2[] = new int[nums.length];
        dp2[0] =0;
        dp2[1] = nums[1];//因为dp2 是没选nums[0] 所以dp2[1] 是必然选择了nums[1]的

        for(int i=2;i<dp2.length;i++){

            if(i==dp2.length-1){
                //因为dp2中的dp1[0]是没有选择的，所以这个地方是可以选的，但前一个不能选
                dp2[i]= dp2[i-2]+ nums[i];
            }else{
                dp2[i]= Math.max(dp2[i-2]+ nums[i],dp2[i-1]);
            }
        }

        return Math.max( dp2[nums.length-1],dp1[nums.length-1]);


    }


}
